package _hash

class leetcode_454 {
    /**
     * https://leetcode.cn/problems/4sum-ii/description/
     * https://programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html
     *
     * 454. 四数相加 II
     *
     * 给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
     *
     *
     * 输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
     * 输出：2
     *
     * 输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
     * 输出：1
     */
    fun fourSumCount(nums1: IntArray, nums2: IntArray, nums3: IntArray, nums4: IntArray): Int {
        /**
        loop a + b : map 1(a + b, count)
        loop c , d : 0-(c + d)
        if( item  in map1){
        map1 ++
        }
         */
        // TODO: HashMap not Map
        // T - N的平方
        // S - N
        val map:HashMap<Int,Int> = HashMap<Int,Int>()
        var result:Int = 0
        for(n1 in nums1){
            for(n2 in nums2){
                map[n1 + n2] = map.getOrDefault(n1 + n2,0) + 1
            }
        }

        for(n3 in nums3){
            for(n4 in nums4){
                // TODO : + , not *
                result = result + map.getOrDefault(0 - n3 - n4,0)
            }
        }
        return result
    }
}